package listbyorder.access201_300.test215;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/23 21:47
 */
public class Solution2 {

    // 方法二： 快排的思想求解
    public int findKthLargest(int[] nums, int k) {
        return quickSort(nums, 0, nums.length - 1, k);
    }

    private int quickSort(int[] nums, int start, int end, int k) {
        int i = start;
        int pivot = nums[end];
        for (int j = start; j < end; j++) {
            if (nums[j] >= pivot) {   // 大于等于的时候放到前面去
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                i++;
            }
        }
        int temp = nums[i];
        nums[i] = pivot;
        nums[end] = temp;
        // 左边大于右边的数据量一共有多长
        int count = i - start + 1;
        if (count == k) {
            return nums[i];
        }
        if (count < k) {
            return quickSort(nums, start + count, end, k - count);
        } else {
            return quickSort(nums, start, i - 1, k);
        }
    }
}
